#!/usr/bin/env python
# -*- coding: utf-8 -*-

# @Time     :2020/10/05
# @Author   :Changshu
# @File     :practice_206.py
# 反转一个单链表。
# 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

class ListNode:
	def __init__(self,x):
		self.val=x
		self.next=None


def printList(head:ListNode):
	p=head
	while p:
		if p.next is not None:
			print(p.val,end='->')
		else:
			print(p.val)
		p=p.next

'''迭代
def reverseList(head:ListNode)->ListNode:
	if head is None:
		return None
	pre=None
	cur=head
	while cur:
		t=cur.next
		cur.next=pre
		pre=cur
		cur=t
	return pre
'''

'''递归--太难想了-_-#'''
def reverseList(head:ListNode)->ListNode:
	if head is None or head.next is None:
		return head
	p=reverseList(head.next)
	head.next.next=head
	head.next=None
	return p

if __name__ == '__main__':
	node1=ListNode(1)
	node2 = ListNode(2)
	node3 = ListNode(3)
	node4 = ListNode(4)
	node5 = ListNode(5)

	node1.next=node2
	node2.next = node3
	node3.next = node4
	node4.next = node5

	# printList(node1)
	node=reverseList(node1)
	printList(node)